//
// Heap Sort
// Created by Win10 on 2023/4/7.
//

#ifndef C_DATA_STRUCTURE_HEAP_SORT_H
#define C_DATA_STRUCTURE_HEAP_SORT_H


#include <algorithm>

#define PARENT_IDX(i) ((i-1)>>1)
#define LCHILD_IDX(i) ((i<<1)+1)
#define RCHILD_IDX(i) ((i<<1)+2)

template<typename T>
//整数或浮点数皆可使用
void sink(T a[], int start, int end) {
  //建立父节点指标和子节点指标
  int parent = start;
  int child = LCHILD_IDX(parent);
  while (child <= end) {//若子节点指标在范围内才做比较
    if (child + 1 <= end && a[child] < a[child + 1]) child++;//先比较两个子节点大小，选择最大的
    if (a[parent] > a[child]) return;//如果父节点大於子节点代表调整完毕，直接跳出函数
    else { //否则交换父子内容再继续子节点和孙节点比较
      std::swap(a[parent], a[child]);
      parent = child;
      child = LCHILD_IDX(parent);
    }
  }
}

template<typename T>
//最大堆排序后是升序
void heap_sort(T a[], int len) {//初始化，i从最後一个父节点开始调整
  for (int i = PARENT_IDX(len - 1); i >= 0; i--)
    sink(a, i, len - 1);//先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
  for (int i = len - 1; i > 0; i--) {
    std::swap(a[0], a[i]);
    sink(a, 0, i - 1);
  }
}

#endif //C_DATA_STRUCTURE_HEAP_SORT_H
